%-*-coding: utf-8-*-

\documentclass[a4paper]{article}
\usepackage{CJK}
\usepackage{a4wide}
\usepackage{graphicx}
\usepackage{fancyhdr}
\usepackage{indentfirst}
%\usepackage{ccmap}
\usepackage[pdftex,
CJKbookmarks,
%pagebackref,
colorlinks,
linkcolor=blue]{hyperref}

\begin{document}
\begin{CJK*}{UTF8}{song}
  \renewcommand{\contentsname}{目录}
  \renewcommand{\abstractname}{摘要}
  \renewcommand{\refname}{参考文献}
  \renewcommand{\figurename}{图}

  \bibliographystyle{plain}
  \nocite{*}

  \title{多天线多信道无线Mesh网络：问题与方案}
  \author{徐家强~~~2007210700\\郭佳~~~2007210740}
  \date{}
  \maketitle

  \begin{abstract}
    与传统的单天线或者单信道无线多跳网络相比，多天线多信道（Multi-Radio Multi-Channel, MRMC）无线Mesh网络具有网络容量大、空时复用程度高的优势。本文对MRMC技术给研究界带来的研究挑战以及当前的解决方案进行了总结，主要包括网络容量的理论建模、信道分配和路由技术，并且对未来的研究方向进行展望。
  \end{abstract}

  \tableofcontents{}

%  \clearpage{}

\section{引言}
\label{sec:intro}


% \section{多天线多信道无线Mesh网络的优势与挑战}
% \label{sec:MRMC-intro}
基于IEEE 802.11的无线局域网已经在日常生活中得到广泛的应用，正是由于无线技术在局域网领域的成功应用，促使人们进一步研究用无线技术来构造城域网和广域网。但是由于无线信道自身物理属性的限制，无线城域网和广域网在技术上还存在很多挑战。在这一节里，作者通过比较单天线单信道、单天线多信道、多天线多信道这几种技术对网络性能的影响，说明多天线多信道（Multi-Radio Multi-Channel, MRMC）技术的优势，最后指出这种新技术对Mesh网络研究领域提出的挑战。

传统的Ad hoc网络研究都基于单天线单信道的假设。但是，单一信道一直是Ad hoc网络的性能瓶颈。Gupta等人的通过模拟实验指出，在$n$个节点的单信道802.11 Ad hoc网络中，单个节点的吞吐量为$O(1/n^\alpha)$，其中$\alpha$和网络的拓扑有关\cite{Gupta:01}。理论分析表明，对一个纯粹Ad hoc网络来说，在随机流作用下，$\alpha=0.5$\cite{Gupta:00}。当$n$个节点形成直线拓扑时，$\alpha=1$，也就是说单个节点的吞吐量和节点数量成反比。上述的结论都基于以下假设：所有节点都互相干扰，而且任何两个节点之间通信的概率相同。在实际的网络中，只有小规模的网络才有可能出现上述情况，对于大规模的网络，节点之间的通信往往是“本地的”，也就是可以对信道进行空间复用。但是在单信道的前提下，空间复用的程度会受到限制，因为所有节点都在同一个信道上通信。如果节点能工作在不同的信道上，原来互相干扰的节点可以通过使用不同信道来避免干扰，所以，多天线和多信道的引入对空间复用性的提高是很有意义的。

虽然使用多信道能提高网络的空间复用程度，但是只是使用多信道而不使用多天线还是会产生限制。如图\ref{fig:fig1}所示，一个流从节点1指向节点3，有两个信道可用，节点1和节点2之间用信道1通信，节点2和节点3之间用信道2通信，但三个节点都只有一个天线。由于天线的物理性质限制，无线信道是半双工的，也就是说不能同时接收和发送。假如节点的发送速率是$R~bps$，由于节点2只能有一半时间从节点接收数据，一半时间向节点3发送数据，整个流的速率就会降低为$R/2~bps$。使用单天线还有一个额外的限制，就是需要频繁地切换信道，增加了端到端延迟。

\begin{figure}
  \centering
  \includegraphics[scale=0.7]{fig/fig1.pdf}
  \caption{流内干扰示例}
  \label{fig:fig1}
\end{figure}

为了克服上述的两个限制，需要为每个节点增加天线的数量。在图\ref{fig:fig1}的例子中，如果节点2有两条天线，那么接收和发送就可以并发进行，流的速率就能够保持在$R~bps$。可见，多天线多信道系统能够有效地提高网络的空间复用程度，从而提高网络吞吐量。而且，由于技术的发展，多天线多信道在技术上和经济上都变得越来越可行，所以，当前的多数无线Mesh网络研究都是针对多天线多信道条件进行的。

虽然多天线和多信道技术有很多技术上的优势，但是如何利用这些优势来实质提高网络的性能为研究者带来了更多的挑战。
\begin{itemize}
\item \textbf{网络容量建模和分析}~~这个问题在无线网络领域已经有了很多研究成果\cite{Gupta:00}\cite{Gupta:01}，而在多天线多信道环境下，对网络容量的分析又有了新的挑战。\textbf{该问题可以表述为：给定网络拓扑、节点数量、天线和信道数量，该网络的容量上限是多少？}在容量上限确定的前提下，研究界已经提出了很多网络设计方案来尽可能逼近该上限，主要包括信道分配和路由策略。
\item \textbf{信道分配问题}~~由于网络节点有多条天线，每条天线可以使用不同的信道，天线和信道的绑定策略，即信道分配，自然成为多天线多信道无线网络中的特有问题。
\item \textbf{路由技术}~~路由算法一直是无线多跳网络的研究热点，这些路由算法稍加修改就可以在多天线多信道环境下使用，需要更多关注的是路由算法的选路标准(routing metrics)，选路标准必须尽量准确地反映各种对路径的质量有影响的因素，这样才能提高网络的路由性能。
\end{itemize}

本文以下几节组织如下：第\ref{sec:model}节总结了当前关于多天线多信道无线多跳网络容量分析和建模的成果，第\ref{sec:CA}节讨论具体的信道分配策略，第\ref{sec:routing}节讨论MRMC网络的路由技术，第\ref{sec:conclusion}节对当前成果作出总结并指出未来的研究方向。

\section{网络容量模型}
\label{sec:model}

由于无线信道的共享特性，网络的容量受到诸多因素的限制，所以网络的容量建模和分析一直是无线网络的一个研究热点。网络容量上限的分析对无线Mesh网络研究的意义在于：通过对网络进行建模，能够更深入理解限制网络容量的因素，为网络的设计提供理论指导。

首先需要定义什么是无线网络的容量。在很多的研究中，网络的容量(capacity)和吞吐量(throughput)是可以互换使用的，本文后面也将互换使用这两个术语。当前网络容量的工作定义主要有三种：
\begin{enumerate}
\item 每一秒钟网络所有节点\textbf{主动}产生并发送的数据量之和，单位是$bits/sec$。
\item 每一秒钟网络所有节点\textbf{主动}产生并发送的数据量与传送的距离乘积之和，单位是$bitmeters/sec$。网络传输了$1~bitmeters/sec$意味着，在1秒内将1比特数据传输了1米。
\item 每一秒钟网络中所有数据流上传输的数据量之和，单位是$bits/sec$。每个流的容量等于流上的瓶颈区域的容量，因此这种定义得出的容量一般小于上面的定义。
\end{enumerate}

到目前为止，关于多天线多信道无线Mesh网络容量建模的工作主要分成两类：第一类工作以渐近解的形式给出了网络容量的上限和下限；第二类工作在给定网络拓扑、天线和信道数量的前提下，用特定的算法计算网络容量的确切界限。

\subsection{网络容量的渐近解}
\label{sec:capacity-asym}

早期关于无线网络容量计算的理论工作都是求解渐近上限和下限。虽然渐近解不能对解决方案的设计提供直接指导，但是能够分析清楚限制网络容量的基本因素，从而为网络设计者提供思路上的指导。

Gupta等的经典工作\cite{Gupta:00}给出了单信道单天线条件下无线网络的容量渐近上限。他们的工作基于两个模型：
\begin{itemize}
\item 信道干扰模型（称为“协议模型”）：在信道$x$上从节点$i$到节点$j$的传输是成功的，如果对每一个同时在信道$x$上传输数据的节点$k$而言，以下条件成立
$$d(k,j) \ge (1+\Delta)d(i,j)$$
其中，$d(i,j)$是节点$i$和节点$j$之间的距离，$\Delta$是保证同时传输的节点之间互不干扰的系数。这个模型实际上是802.11的RTS/CTS机制的理论描述。
\item 信道模型：假设所有可用信道的总带宽为$W$，信道数量为$c$，每一个信道分得的带宽为$\frac{W}{c}$，随着信道增加，每个信道获得的带宽减少。
\end{itemize}

% 基于上述模型，Gupta等进一步分析了两种类型的网络拓扑下网络容量的渐近上限。
% \begin{itemize}
% \item \textbf{任意给定的网络}：在这类网络拓扑中，网络的节点分布和数据流都是可以控制的。因此，对这种网络的分析使用于任何的网络拓扑，可以把分析出的上限看作所有网络的上限。在该类拓扑中，网络容量的单位是$bitmeter/sec$。
% \item \textbf{随机网络}：随机网络可以看作是特殊的给定网络（一个已经被生成的随机网络肯定已给定的），因此上面的界在这种网络中依然成立，但是可以推导出更精确的界。随机网络的节点位置和流都是随机生成的。网络的容量用所有流的吞吐量的叠加来计算，单位是$bits/sec$。
% \end{itemize}

对任意给定的网络，其容量上限是$\Theta(W\sqrt{n})~bitmeter/sec$；对随机网络而言，其容量上限是$\Theta(W\sqrt{\frac{n}{\log n}})~bit/sec$。注意上述的界都是紧的，也就是网络容量的下限和上限一致。

Gupta等\cite{Gupta:00}根据理论分析提出一个提高网络容量的指导方针：节点应该只和邻近节点通信。这一个方针引起了研究界的关注，派生出很多研究成果。Kozat等\cite{Kozat:03}和Liu等\cite{Liu:03}分别基于这个结论提出了使用“混合”方式来提高网络的容量。在这类方案中，节点只与邻近的节点直接通信，如果节点要和相隔跳数过多的节点通信，则需要通过连接到有线网络的基站或者接入点。Grossglause等基于上述结论进一步指出：节点的移动能够增加网络的容量\cite{Grossglause:02}。节点只有移动到和目的节点距离足够近时才进行数据传输，这种方案虽然能增加网络容量，但是也大大提高了传输的延迟。

Kyasanur等在Gupta等工作的基础上分析了多天线多信道条件下天线和信道数量对网络容量的影响\cite{Kyasanur:05}。每个节点有$c$信道和$m$条天线的无线网络称为$(m, c)$-网络，它的容量只和$\frac{c}{m}$的值有关，而与具体的$c$和$m$的值无关。同时，一个$(c, c)$-网络的容量和Gupta等得出的容量相等，也即等于$(1, 1)$-网络的容量。

Kyasanur等的分析结果如图\ref{fig:capacity}所示，左图任意给定网络的容量变化，右图是随机网络的容量变化。只要$\frac{c}{m}$的值大于一，一个任意给定的网络容量与$(c, c)$-网络相比存在容量损失。同时，他们的结论也指出，对随机网络而言，当$\frac{c}{m}$在$O(\log n)$的范围内时，网络容量不会出现下降。

% 对任意给定的网络拓扑，有如下的结果：
% \begin{enumerate}
% \item 当$\frac{c}{m}$为$O(n)$时，网络的容量为$\Theta(W\sqrt{\frac{nm}{c}})~bitmeters/sec$（图\ref{fig:capacity}中的A-B段）。与$(c, c)$-网络相比，有因子为$1-\sqrt{\frac{c}{m}}$的容量损失。
% \item 当$\frac{c}{m}$为$\Omega(n)$时，网络容量为$\Theta(W\frac{nm}{c})~bitmeters/sec$（图\ref{fig:capacity}中的B-C段）。由于此时$\frac{nm}{c} \le 1$，所以这种情况下的容量损失大于上一种情况。
% \end{enumerate}

% 对于随机网络拓扑，有如下的结果：
% \begin{enumerate}
% \item 当$\frac{c}{m}$为$O(\log n)$时，网络的容量为$\Theta(W\sqrt{\frac{n}{\log n}})~bits/sec$（图\ref{fig:capacity}中的D-E段）。在这种情况下，和$(c, c)$-网络相比没有容量损失。因此，在很多实际的场景下，由于$c$不会太大（802.11b只提供了12个独立信道），所以假如网络拓扑和流量符合均匀分布的话，每个节点使用一条天线就足够了。
% \item 当$\frac{c}{m}$同时为$\Omega(\log n)$和$O(n(\frac{\log \log n}{\log n})^2)$时，网络的容量为$\Theta(W\sqrt{\frac{nm}{c}})~bits/sec$（图\ref{fig:capacity}中的E-F段）。
% \item 当$\frac{c}{m}$为$\Omega(n(\frac{\log \log n}{\log n})^2)$时，网络的容量为$\Theta(\frac{Wnm\log \log n}{c\log n})~bits/sec$（图\ref{fig:capacity}中的F-G段）。
% \end{enumerate}

对上述的结果，有三点需要注意。首先，上述结论使用的信道模型假设随着信道数量的增加，每个信道获得的带宽会减少，这和802.11网络的信道模型不同。Kyasanur等指出，对类似802.11的信道，只需要将结论中的$W$代换成$Wc$，就可以得到相应的结论，推导过程仍然成立。其次，由于物理条件的限制，一个节点上不可能有太多的天线，所以随着信道数量$c$的增大，网络容量会出现下降。再次，由于实际的网络场景一般不符合随机网络的特性，所以考虑实际问题的时候应该参考任意给定网络的结论。


\begin{figure}
  \centering
  \includegraphics[scale=0.6]{fig/capacity.png}
  \caption{天线和信道数量对网络容量的影响}
  \label{fig:capacity}
\end{figure}

\subsection{网络容量确切界限的计算}
\label{sec:capacity-accurate}

虽然容量的渐近界限能够从趋势上预测各种网络参数对网络容量的影响，但是在实际网络的设计过程中，设计者更需要的是一种根据输入参数（网络拓扑、信道、天线等）计算网络容量确切界限的方法，从而帮助确定某一个流量需求是否能实现，或者需要什么参数才能实现。

在Jun等的工作\cite{Jun:03}中，提出了一种基于“冲突域”的概念来计算网络容量界限的方法。在一个无线Mesh网络中，能够进行通信的两个节点之间存在一条“链接”，冲突域的概念是针对一条链接而言的。这里继续使用Gupta等\cite{Gupta:00}提出的“协议模型”作为信道干扰模型。在这个模型下，一条链接的冲突域是指由于这条链接正在通信而必须处于静默状态的网络中其他链接的集合。属于一个冲突域内的所有链接必须共享有限的MAC层带宽$B$，而独立的冲突域之间可以并行通信。

基于冲突域的概念，Jun等分析了以下场景中网络容量的上限：Mesh网络是面向Internet连接构建的，有一个节点作为网关，网络使用单天线单信道。在这种结构的网络中，越接近网关的冲突域流量就会越大，因为其他节点的流都以网关作为目的节点。Jun等定义流量最大的冲突域为“瓶颈冲突域”，网络的容量受到瓶颈冲突域容量的限制。

以图\ref{fig:conflic-domain}中的直线拓扑为例，假设所有节点的自身产生和发送的数据速率为$G~bits/sec$，由于网关的聚集效应，越靠近网关的节点需要转发的数据越多。节点2和节点3之间的链接产生的冲突域如图中阴影部分所示，由于它承担的数据量最大，所以是瓶颈冲突域。该冲突域的数据发送总速率为$30G$，而MAC层的带宽为$B$，故有$30G \le B$，得出每个节点自身产生和发送的数据速率（即容量）上限为$\frac{B}{30}$。上述的方法很容易推广到非直线拓扑和多个网关的情况。

\begin{figure}
  \centering
  \includegraphics[scale=0.8]{fig/conflict.png}
  \caption{直线拓扑中的冲突域}
  \label{fig:conflic-domain}
\end{figure}

上述工作提出的冲突域概念是很有用的，但是该工作本身还存在一些局限：首先，他们假设所有节点自身按照相同速率产生数据，而且假设信道能够完全公平地在节点之间分配，没有详细考察公平性问题。其次，他们没有考虑冲突域内的信道空间复用。例如，图\ref{fig:conflic-domain}中的节点5和节点1能够同时发送数据。再次，他们只考虑了网络中只存在一个瓶颈冲突域的情况。

针对上述问题，Aoun等对Jun等的工作进行了扩展\cite{Aoun:06}。与Jun等相比，他们采用了基于流的分析方法，而不是采用基于链接的分析方法。他们首先定义了一个与Kodialam等的工作\cite{Kodialam:05}中类似的网络模型，然后基于Max-Min流间公平模型来分配网络的带宽，从而保证分配结果的流间公平性。在上面这些模型的基础上，他们重新定义了瓶颈冲突域的概念，最后用冲突域来计算网络的容量上限（所有流的容量之和）。

上述的两个工作都没有考虑多天线多信道的环境，Akhtar等的工作基于冲突域的概念进一步考虑了这个问题\cite{Akhtar:08}。但是，他们的工作还存在一些局限：他们没有给出具体的计算容量的算法，而只是给出了通过仿真得到的结果；没有对冲突域模型在多天线多信道的环境下进行扩展。在多天线多信道环境下对冲突域模型进行完善是一个可能的研究方向。

与上述的几个不同，Kodialam等没有使用冲突域的概念来计算网络容量的上限\cite{Kodialam:05}。他们首先为多天线多信道多跳无线网络建立了一个模型，并且给出了一个端到端的流速率要求可实现的充分必要条件。在此基础上，他们提出了一个判断网络的优化目标是否可行的框架，并且以端到端的流速率要求为例子，给出了计算一个网络可实现的流速率分配上限的算法。Kodialam等的工作和上面的几个工作在本质上是相同的，都是用网络参数作为限制条件，计算网络容量的确切界限，在此过程中需要为网络的限制条件（流、干扰、链接等）建立一个数学模型。

\subsection{容量建模和分析的启示}
\label{sec:inspiration}

对多天线多信道无线Mesh网络而言，当网络拓扑、天线和信道数量及分布这几个条件给定之后，网络容量的上限就可以确定。限制网络容量的因素有两方面，一个是网络的设计参数，比如拓扑、天线、信道等，另一个是MAC的信道争用机制。因此，如果要从本质上提高网络的容量，必须从这两方面入手：合理调整参数或者使用更先进的信道争用机制。

信道的争用和信道的分配是需要区分的两个问题。信道的争用解决的是频率资源的共享问题，使用同一个信道的节点之间需要争用信道，这个问题只能在MAC层处理；信道的分配解决的是不同的信道如何于天线绑定的问题，是多天线和多信道特有的问题。本文只关注信道的分配，而不关注信道的争用。

假设信道争用机制不变（符合“协议模型”），那么只要网络参数给定，各种具体的路由算法和信道分配方法所能实现的最大容量都不会超过网络本身的上限。正是由于网络参数对容量有重要影响，所以在设计具体的路由算法和信道分配策略的时候，必须考虑这些因素，针对实际网络设计解决方案。

\section{信道分配}
\label{sec:CA}

在多天线和多信道的环境下，信道分配成为一个特有的问题，高效的信道分配方案能够最大程度上利用有限的网络容量。研究界当前的信道分配方案可以从三个角度加以分类：
\begin{itemize}
\item \textbf{从网络层次上分}~~信道分配可以在MAC层完成，也可以在MAC层以上完成；
\item \textbf{集中式和分布式}~~集中式的算法需要网络中有一个实体掌握整个网络的信息，然后协调所有节点进行分配；而分布式算法则由每个节点根据自己的局部信息来决定信道分配；
\item \textbf{静态和动态}~~使用静态的方案分配的信道会一直不改变或者在很长一段时间内不会调整，而动态的方案则可以根据网络状态动态调整信道分配。
\end{itemize}

MAC层协议可以根据信道的状态（干扰、使用程度等）为每一个报文选择合适的发送信道。这类方案的优势在于实时性，MAC层可以对信道的变化作出最及时的反应。由于MAC层只能得到网络的局部信息，所以MAC层的方案都是分布式的。当前研究界提出的MAC层信道分配方案可以分成两类：基于握手的和基于跳频的。动态信道分配协议(Dynamic Channel Assignment, DCA)\cite{wu2000nmc}、多信道CSMA MAC(multichannel CSMA MAC)\cite{so2004mcm} 以及多信道MAC(multichannel MAC)\cite{jain2001mcm} 都是基于握手的MAC层信道分配的例子。RICH-DP(Receiver-Initiated Channel-Hop with Dual Polling)\cite{bahl2004sss} 和SSCH(Slotted Seeded Channel Hopping)\cite{tzamaloukas2001ric} 是基于跳频的例子。

但是，MAC层的信道分配方案也有比较大的局限性。首先，MAC层只能得到邻居节点的信息而没有网络的全局信息，所以不能产生全局优化的分配结果；其次，MAC层上的信道分配需要节点之间进行紧密的时间同步，难于实现；再次，这些协议都要求对802.11 MAC层作改动，所以不能使用廉价的802.11网卡来实现。

在MAC层以上进行信道分配其实是将信道分配的策略和信道分配的机制分离，有MAC层以上的层次决定如何分配信道，具体的信道切换工作则由MAC层完成。与MAC层的信道分配方案相比，这类方案的优势在于：
\begin{itemize}
\item 上层可以利用路由和流量信息来优化信道分配；
\item 与MAC层相比，上层进行信道分配的时间尺度比较大，因此无须节点之间的紧密时间同步；
\item 由于分离了策略和机制，MAC层既可以使用多个802.11的网卡也可以使用专门定制的MAC硬件。
\end{itemize}

当前研究界的成果大多数都属于MAC层以上的方案，下面按照集中式和分布式的分类方法来介绍这些研究成果。

\subsection{集中式的信道分配算法}
\label{sec:centralized}

集中式的算法假设有一个实体掌握网络的全局信息，从全局优化的角度来进行信道的分配。这个实体可以是设计者，也可以是网络中的一个中心服务器。由设计者进行的集中式分配都是静态的，因为网络一旦运行，很长一段时间内配置不会改变；如果信道分配由网络中的一个节点来协调，那么分配可以是动态的，该节点协调其他节点重新分配信道。

从优化的目标来看，当前使用的主要有两种：
\begin{enumerate}
\item \textbf{网络的干扰最小化}~~正如在第\ref{sec:model}节分析所示，干扰是限制无线网络容量的根本因素。所以如果信道分配方案能尽量逼近干扰的下限，那么网络的容量就能尽量逼近上限。\cite{Mahesh:05}，\cite{Subramanian:07}，\\ \cite{Ramachandran:06}，\cite{Ko:07}都将减少干扰作为优化的目标。
\item \textbf{网络的容量最大化}~~使用这个目标需要把网络的期望负载作为先验条件，通过流量工程的方法实现网络容量的最大化。以此作为优化目标的工作包括\cite{Raniwala:04}，\cite{Alicherry:05}，\cite{meng2006jra}。
\end{enumerate}

\subsubsection{最小化网络干扰的算法}
\label{sec:min-interference}

以最小化网络干扰为目标的信道分配算法依赖于网络的拓扑模型，这些研究中使用的拓扑模型对其他的信道分配方案研究也是有用的。

Marina等的工作\cite{Mahesh:05}基于网络的三种图表示：
\begin{itemize}
\item \textbf{连接图(connectivity graph)}~~在这种图示中，如果两个网络节点在通信范围之内，则在图中有一个对应的连接；
\item \textbf{冲突图(conflict graph)}~~该图示的节点代表连接图中的一条连接，如果一条连接的通信会对另一条连接造成干扰，则存在一条连接这两个连接对应的节点的边。冲突图中的边有一个权值，表示两个连接之间的干扰程度，干扰的计算基于Gupta等的“协议模型”\cite{Gupta:00}；
\item \textbf{拓扑图(topology graph)}~~这个图指信道分配后形成的网络拓扑分布，如果两个节点被分配了一个共同信道并且能够通信，则存在一条连接它们的边，这个图是连接图的子图。
\end{itemize}

在图\ref{fig:conflict-graph}中，上方的是连接图，下方的是冲突图，由于连接$ij, jp, pq$之间互相干扰，因此形成了如图所示的冲突图，节点$ij, jp, pq$分别代表三条连接。

\begin{figure}
  \centering
  \includegraphics[scale=0.7]{fig/conflict-graph.pdf}
  \caption{连接图和冲突图}
  \label{fig:conflict-graph}
\end{figure}

Marina等信道分配问题形式化为拓扑控制问题，通过信道的分配形成一个干扰最少的拓扑，限制条件为保持网络的连通性。这和图着色问题类似，而且他们证明了这是一个NP完全问题。接下来，他们提出一种贪心算法CLICA来求解该问题。算法的总体思路是，按照节点上天线数量从多到少的顺序遍历节点，为每个节点选择干扰最少的信道-天线组合，同时要求保持连接图上的所有边。

Subramanian等的工作\cite{Subramanian:07}和上一个工作使用基本同样的网络模型，只是冲突图的边没有权值，他们的优化目标是使网络中互相干扰的连接数最少，也就是在冲突图中的边数最少。他们更加形式化地描述了信道分配问题以及优化目标。他们把信道分配问题抽象成对冲突图的点着色问题，同时要求满足节点上天线数量的限制。

Subramanian等基于图论中求解点着色问题的Tabu搜索技术开发了一个集中式算法用于分配信道，算法输入为冲突图。为了更好地评价算法的性能，他们分别使用整数线性规划和半确定性规划的方法来求解一个冲突图的干扰下界。

在实际的Mesh网络中，不但需要考虑Mesh节点之间的干扰，还需要考虑网络以外无线信号的干扰。基于以上观察，Ramachandran等提出需要针对干扰情况的变化动态调整Mesh网络的信道分配\cite{Ramachandran:06}。

Ramachandran等首先对广泛使用的冲突图模型进行了扩展，提出多天线冲突图(Multi-radio Conflict Graph, MCG)模型。这个模型实际上是对冲突图模型的细化，图中的节点表示两个网络节点上的一对天线，而不是原有模型中的连接图中的一条连接。这样做的好处是可以自然地将天线数量的限制加入到点着色算法中。

Ramachandran等提出了一种由一个中心节点（称为信道分配服务器，CAS）协调的信道分配机制。具体地说，各个Mesh节点定期探测自己感知到的网络以外信号对每一个可用信道的干扰，然后对信道质量进行评价，并将评价发送给CAS，CAS定期根据收集到的干扰情况重新计算信道分配方案，并通知其他节点改变信道分配情况。信道分配方案由CAS通过运行一个对MCG进行广度优先遍历的算法产生。

但是，动态调整天线上的信道会引起一些问题，其中最重要的一个是会中断正在传输的数据流。为了缓解这个问题，Ramachandran等提出保留一个信道作为“默认信道”，在原来的天线切换信道时，原有数据先通过默认信道进行通信。这种机制称为“连接重定向”。

Das等\cite{Das:05}研究了信道的静态分配问题，即信道在分配之后不再改变。由于信道数、天线数、节点数都是整数，所以他们用两种方法将该问题抽象成整数线性规划问题。问题的限制条件包括天线数量、信道数量以及一条天线只能分配一个信道的事实，优化的目标是最大化网络中能够同时活跃的连接的数量。

\subsubsection{最大化网络容量的算法}
\label{sec:max-capacity}

最小化网络干扰的算法只利用了网络的拓扑信息，而没有利用网络层所提供的路由和网络流量信息，所以还不能根据网络的运行状况最大程度地优化信道分配方案。因此，很多研究者提出需要联合设计信道分配、路由和连接调度方案，整体优化网络设计的性能。

Raniwala等认为在信道分配的过程中，需要考虑网络的流量情况，而不是单纯考虑信道干扰情况\cite{Raniwala:04}。基于上述观察，他们以最大化网络中数据流的吞吐量为优化目标来指导设计信道分配算法。他们采用流量工程的方法结合贪心策略来给每一个连接分配信道，他们的算法需要网络拓扑和数据流的期望吞吐量作为输入。具体地说，给定网络拓扑和每个连接的期望负载（从数据流的期望吞吐量估计得到或者基于路由计算得到），信道分配策略会按照负载从高到低的顺序遍历所有连接，给每个连接分配一个干扰最少的信道。信道分配的结果会作为路由算法的输入，路由算法为每个流计算出满足吞吐量要求的路由。从路由结果可以计算出每个连接的负载，而这些负载又作为信道分配算法的输入。上述迭代过程直到数据流流量之和收敛结束。

Alicherry等以最大化网络的容量为目标，设计一个多步的算法联合求解路由、信道分配和连接调度的问题\cite{Alicherry:05}。对网络中的每一个节点$u$，期望的用户负载为$l(u)$。如果把优化目标设定为最大化网络中所有节点的吞吐量之和，有可能会影响用户之间的公平性，有些用户会饥饿。基于上述观察，他们提出一个新的优化目标：最大化$\lambda$，使得每个节点都至少能实现$\lambda l(u)$的吞吐量。

Alicherry等的算法分为三个主要步骤：计算网络网络中每一条连接上的负载$f(e(i))$，$f(e(i))$表示当边被分配了信道$i$以后上面的流量，需要注意，这一步的信道分配不考虑天线数量的限制，而只是保证连接之间无干扰；接下来再考虑现实的信道分配问题，通过调整上一步的信道分配结果，使之变得可实现，但可能会增加干扰，干扰的增加被控制在最小程度；解决连接调度问题，保证同一个时间片内没有两条处于对方干扰范围内的连接在同一个信道上发送数据。

Meng等\cite{meng2006jra}提出了一种对连接调度问题形式化的方法——调度图(scheduling graph)，调度图的生成基于一种类似于MCG\cite{Ramachandran:06}的扩展冲突图模型。在扩展冲突图模型中，每个图节点代表网络中两条天线之间的连接，而不是网络中两个节点之间的连接，即一个节点上的多条天线被分别考察。调度图可以由扩展的冲突图加上冲突图上每条连接需要占用的时槽数确定。

在调度图的基础上，他们将连接调度问题形式化为调度图的点着色问题，进而提出了一种调度要求可实现的必要条件。结合扩展冲突图以及期望的端到端网络流量信息，他们提出一种线性规划算法来求解联合的信道分配、路由和调度问题。

\bigskip{}

虽然能够利用全局信息进行优化，但是集中式的信道分配方案有一定的局限性：
\begin{itemize}
\item 对于静态的方案而言，不能适应网络环境的动态变化（如干扰和流量变化）；
\item 对于动态的方案，需要有一个中心节点协调全网络的节点，难于实现；
\item 很多方案需要一个期望的流量分布作为输入，这在实际场景中往往是不现实的。
\end{itemize}

针对上述局限，很多研究者提出了分布式的信道分配算法。

\subsection{分布式信道分配算法}
\label{sec:distributed}

Kyasanur等提出了一种分布式的动态信道分配方法\cite{Kyasanur:05-2}。每个节点的可用天线分成两部分，一条天线绑定在一个固定信道上，称为“固定天线”，其他天线的信道都可以动态调整。当一个节点要和邻居节点通信的时候，需要将一条可变信道的天线切换到邻居节点的固定信道上。

这种方式的优点是简单，不需要节点之间的同步，但是缺点是基于直觉，不能保证网络性能的最优化。

Raniwala等提出了一种分布式动态的信道分配方案\cite{Raniwala:05}。他们首先把信道分配的过程再细分成两个阶段：接口-邻居绑定和接口-信道绑定。接口-邻居绑定是指，节点确定使用哪个接口和哪个邻居进行通信；接口-信道绑定是指，节点确定每个接口使用哪个信道进行通信。

接口-邻居绑定阶段需要解决的关键问题是节点之间的“信道依赖”问题。信道依赖问题如图\ref{fig:channel-dependency}所示，假设节点E只有两条天线，当节点D决定将DE之间的连接改到信道7上时，节点E和节点H之间的连接也需要改用信道7，引起信道的连锁改变。他们通过将节点的可用接口划分为两个不相交子集来解决“信道依赖”问题。在他们的方案中，所有节点形成一棵路由树，节点的部分接口只用于和树中的父节点通信，部分接口只用于和树中的子节点通信，这样当任何一个子集中的接口需要改变信道的时候，另一个子集中的接口信道可以保持不变。

\begin{figure}
  \centering
  \includegraphics[scale=0.5]{fig/channel-dependency.png}
  \caption{信道依赖问题}
  \label{fig:channel-dependency}
\end{figure}

在接口-信道绑定阶段，每个节点根据收集到的周边节点的信道使用状况，为每个接口选择负载尽可能低的信道。因为在Mesh网络中，越接近互联网网关的节点负载会越重，所以到网关跳数越小的节点在信道分配是优先级越高。节点进行接口-信道绑定时，会避免与处于自己冲突域内的比自己优先级高的节点使用相同的信道，这样就确保优先级高的节点能得到更多的带宽。

在多天线多信道的Mesh网络中，路由协议依赖于信道分配产生的网络拓扑，而信道分配又依赖于网络中连接的负载，从而依赖于路由协议的结果。由于路由和信道分配互相依赖，所以必须对这两个问题进行综合考虑。基于上述观察，Wu等提出了一种分布式、动态的联合信道分配和路由方案\cite{wu2006dca}。

首先，他们定义了一个反映信道利用状况的量化指标CCM(Channel Cost Metric)。对一种信道分配和路由的组合方案，可以计算它的CCM，CCM越小，该方案信道利用程度越高。基于CCM，他们提出了一种分布式算法，节点选择具有局部最小CCM一种信道分配和路由组合。

Wang等提出了一种分布式的联合信道分配、路由和调度算法(joint channel assignment, routing and scheduling, JARS)\cite{Wang:08}。他们采用按需路由，在路由建立的过程中同时进行信道分配和连接调度，其选路的标准则根据信道分配和连接调度的结果计算得出。他们的方案使用了基于调度的MAC层协议，而不是传统的基于退避的MAC层协议，因此需要使用专用的MAC，而且要求节点之间进行同步。

上述关于联合的信道分配和路由的工作都只是考虑了通过提高信道多样性(channel diversity)来优化网络的容量，在Chen等的工作中，进一步提出需要将网络的动态拓扑控制和信道分配、路由进行联合考虑\cite{chen2007jtc}。通过恰当地改变天线的发射功率，可以改变网络的拓扑，提高信道的空间复用程度(spatial reusability)。信道分配和拓扑控制会影响网络的拓扑，因此会影响路由决策，而路由决策则会影响网络的负载分布，反过来影响信道分配和拓扑控制。所以，必须针对这几个问题进行联合设计，这三种决策的一个组合成为一个配置。他们在CCM的基础上加入了对空间复用性的评价，提出了一种新的判定一个配置质量的标准——ECATM(Equivalent Channel Air Time Metric)。他们实现了一种分布式的算法，节点自动选择ECATM值较小的配置。

上述的分布式方案都是基于直觉的。Subramanian等提出一种分布式贪心算法(Distributed Greedy Algorithm)\cite{Subramanian:07}。图论中的最大K-切割问题(Max K-cut Problem)是指将图划分成K个分区，要求最大化两个端节点在不同分区中的边的数目。信道分配问题可以形式化为增加了天线数量限制的、对冲突图的最大K-切割问题。在这里，可以把冲突图中分配了相同信道的节点（连接）看作属于同一个分区，而整个网络的干扰就是两个端节点在同一个分区中的边的数目。基于这个观察，他们基于经典的图论算法设计了分布式贪心算法。

\bigskip{}

相对于集中式的信道分配方案而言，分布式的分配方案具有动态性好、布置方便的优点，但是主要问题是缺少全局信息，因此算法更难得到优化的结果。目前多数的方案都是启发式的，分布式的优化算法还有待研究。

\section{路由技术}
\label{sec:routing}

尽管在单信道多条无线网络领域中已经有了很多关于路由技术的研究，但是，这些技术在多天线多信道的条件下并不能保证产生高效率的路由结果。这主要是由于原有的路由技术没有考虑多天线多信道环境的特点：
\begin{itemize}
\item 在多天线多信道网络中，节点上不同的天线可以工作在不同信道上，因此网络中的连接使用的信道可以各不相同。处于干扰域内的连接如果使用相同信道就会互相干扰，导致吞吐量下降。因此，一条跳数较少但是所有连接都使用同一个信道的路径，其质量不一定比一条跳数较多但不同连接使用不同信道的路径好。所以，在多天线多信道的路由设计中，必须加入对“信道多样性”的考虑。
\item 在多天线多信道网络中，网络的拓扑是由信道分配的结果决定的。因此，如果路由算法和信道分配算法不能很好配合，也不能高效地利用网络的容量。路由算法和信道分配算法是互相关联的两个问题。
\end{itemize}

由于路由和信道分配是紧密联系的，很多研究者提出了路由和信道分配的联合设计方案，\cite{Raniwala:04, Alicherry:05, meng2006jra}是集中式方案的例子，\cite{wu2006dca, Wang:08, chen2007jtc}则是分布式方案的例子，这些方案已经在\ref{sec:max-capacity}节和\ref{sec:distributed}节中介绍。为了让路由算法更好地适应多天线和多信道的环境，路由算法使用的选路标准必须作出相应调整。

\subsection{路由选路标准}
\label{sec:routing-metrics}

路由算法一直是无线多条网络的研究热点，这些路由算法稍加修改就可以在多天线多信道环境下使用，需要更多关注的是路由算法的选路标准(routing metrics)，选路标准必须尽量准确地反映各种路径的质量，这样才能提高网络的路由性能。研究界针对多天线多信道网络提出了很多选路标准。

\subsubsection*{跳数(Hop Count)}
\label{sec:hop}

跳数是最常用的选路标准，它的主要优点是简单，但是在无线的路由协议中，使用跳数作为选路标准有其局限性。由于无线网络中不同连接之间带宽的差异，以及信道干扰和丢包现象的存在，使得不同的连接的质量各不相同，而跳数少的路径上连接的质量可能不如跳数多的路径，因此选择跳数少的路径有可能会导致端到端的吞吐量下降和延迟增大。

\subsubsection*{平均传输次数(Expected Transmission Count, ETX)}
\label{sec:etx}

ETX\cite{couto2005htp}测量在一条无线连接上成功传输一个数据包需要的传输次数（包括重传），一条路径的ETX等于路径上所有连接的ETX之和。节点通过向邻居节点发送试探包测量连接的正向和反向的丢包概率$P_f$和$P_r$，ETX值由下式决定：
$$ETX = \frac{1}{P_f \times P_r}$$

由于路径长度和路径的丢包率都会影响ETX的值，因此这个选路标准同时考虑了跳数和信道质量两个方面。但是，它也没有把干扰的因素考虑进去，也没有把不同连接的带宽考虑进去。

\subsubsection*{平均传输时间(Expected Transmission Time, ETT)}
\label{sec:ett}

ETT\cite{draves2004rmr}选路标准加入了对不同连接的带宽的评价。ETT和ETX之间的关系可以用下式表示：
$$ETT = ETX \frac{S}{B}$$

其中，$S$表示传输数据包的大小，$B$表示连接的带宽。通过引入参数$B$，可以使得选路标准反映连接的容量状况，选择高容量的连接有利于提高路由的吞吐量。但是这个选路标准还是没有把干扰的因素考虑进去。

\subsubsection*{加权累加ETT(Weighted Cumulative ETT, WCETT)}
\label{sec:wcett}

WCETT\cite{draves2004rmr}选路标准第一个将信道多样性(channel diversity)引入选路标准设计中。为了减少数据流的流内干扰，WCETT减少一个数据流内使用同一个信道的连接数目。假设一条路径有$N$条连接和$K$个信道，路径的WCETT的计算公式如下：
$$WCETT = (1 - \beta)\sum_{i=1}^NETT_i + \beta\max_{1 \le j \le K}X_j$$

其中，$\beta$是一个权值，$X_j$是路径上使用信道$j$的连接的数目。$\max_{1 \le j \le K}X_j$表示路径上使用最多的信道的使用次数，这个值越小，路径上的流内干扰就越小。但是，这个选路标准没有把流间的干扰加以考虑。而且，它假设一条路径上的所有使用相同信道的连接都在一个干扰域内，这对于比较长的路径而言是不成立的。

% \subsubsection*{干扰及信道切换选路标准(Metric of Interference and Channel-switching, MIC)}
% \label{sec:mic}

% MIC\cite{yang2005drm}选路标准改进了WCETT标准，加入了对流间干扰考虑。一条路径的MIC计算如下：
% $$MIC = \frac{1}{N \times \min ETT}\sum_{i=1}^NIRU_i + \sum_{i=1}^NCSC_i$$

% 其中，$N$是网络中节点的个数，$\min ETT$表示网络中最小的$ETT$值。MIC包含两个主要部分，一个是IRU(Interference-aware Resource Usage)，一个是CSC(Channel Switching Cost)。

\subsubsection*{归一化瓶颈连接带宽(Normalized Bottleneck Link Capacity, NBLC)}
\label{sec:nblc}

NBLC\cite{liu2006car}选路标准考虑了信道之间的负载均衡问题，其主要思想是通过使网络的流量在节点和信道之间尽可能平均分配，从而提高网络的吞吐量。一条路径$p$的NBLC值计算如下：
$$NBLC_p = \min_{link i \in p}(\frac{RLC_i}{CEBT_{i, p}}).\gamma^L$$

其中，RLC(Residual Link Capacity)是指一条连接上信道空闲时间的比例，这个值越大表明该连接可用的容量越大，CEBT(Cumulative Expected Busy Time)是指路径$p$上和连接$i$互相干扰的连接的$ETT$值之和，这个值越大表明路径的流内干扰越严重。因此，路径$NBLC$值越大，表明路径的质量越好。该选路标准综合考虑了路径长度、丢包率、信道多样性和容量等因素。

\subsubsection*{调整的平均传输延迟(Adjusted Expected Transfer Delay)}
\label{sec:aetd}

Zhou等提出了一种新的选路标准——AETD(Adjusted Expected Transfer Delay)\cite{zhou2006csr}。该选路标准综合考虑了一条路由的两个特性：
\begin{itemize}
\item ETD(Expected Transfer Delay)：一个报文的平均传输延迟；
\item EDJ(Expected Delay Jitter)：连续两个报文的传输延迟之间的抖动。
\end{itemize}

路由的ETD综合反映了路由的路径长度以及连接质量，而EDJ可以综合反映路由的信道多样性和连接质量，通过对这两个因素进行加权平均，可以更准确地评价一条路由在多信道环境下的质量。

\subsection{开放的研究课题}
\label{sec:routing-open-issues}

当前路由方面的研究热点主要集中在路由选路标准的设计以及路由与信道分配的联合方案设计两个方面，但是，为了更好地利用多天线多信道网络，还有一些问题需要进一步探讨。

\subsubsection*{QoS路由}
\label{sec:QoS-routing}

Tang等在\cite{tang2005iat}中针对多天线多信道的QoS路由问题提出了一种启发式的流分配算法。但是，在多天线多信道环境下的QoS路由问题依然有很多挑战需要解决。首先，QoS路由需要很好地和信道分配策略结合，其次，对于动态的信道分配策略，链路的信道和带宽随时间而变化，QoS路由也必须动态调整。

\subsubsection*{多径路由和负载均衡}
\label{sec:multi-path}

使用多径路由可以提高端到端的带宽，在多条路径之间进行负载均衡，还可以提高路由的容错性。一般的无线多条网络中的多径路由都只考虑多条路径之间的连接不相交和节点不相交，在多天线多信道环境下，还需要增加一个考虑的维度——信道不相交。由于使用同一个信道的连接可能导致干扰，所以保证多条路径之间在干扰域内的连接不相交可以减少流间干扰，提高吞吐量。So等研究了单天线多信道下的负载均衡路由问题\cite{so2005lbr}，但是他们的工作假设同一条路径上的连接都使用相同的信道，这样会引入较大的流内干扰。

% \section{负载均衡}
% \label{sec:load-balancing}

% 在讨论如何制定策略逼近网络容量上限时，负载均衡是一个不得不考虑的因素。WMN中的负载可以定义为对节点各种资源的消耗，包括节点的带宽，处理能力，存储空间和电池能量等。当前负载均衡面临的问题主要是：未统一负载的WMN降低了有效的数据转发和资源利用。多个数据流在传输中竞争某一特定节点将导致冲突的上升，最终导致网络吞吐量下降。

% 不均衡的负载形式主要包括网关负载和中心负载（瓶颈负载）。导致网关负载的原因是由于网关负责连接WMN和主干网，网关节点自然成为流量的汇聚点，产生负载不均衡。对于内网而言，将导致拥塞，包丢失，缓存溢出等问题；对外网而言，影响网关和外部网络之间的回程连接。导致中心负载的原因主要是由于最短路径路由的算法。最短路径路由尽可能地选择源和目的之间接近直线的路由，靠近网络中心的节点将变为冲突节点，这将导致中间节点的资源消耗相对过大。

% 当前的解决方法也主要针对上面提到的两类不均衡的负载形式。基于网关的负载均衡的解决方案主要一是增建基础设施以增加网关节点，第二既是使用多信道技术。基于中心的负载均衡的解决方案主要是构建相关的网络拓扑和协议以分散网络中心的负荷，其中应用多信道技术有很好的效果。目前应用MRMC技术解决负载均衡的方案较少。So提出了一种单接口多信道网络下的负载均衡路由协议 [1]。

% \subsection{单接口多信道混合无线网络下的负载均衡路由}

% 这种单接口节点协议可以应用在体积小成本低的设备上，如手机，PDA等。网络机构如下图：

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/LHybridWN.jpg}
% \end{figure}

% 图中实线表示工作在信道1上的链路，虚线表示工作在信道2上的链路。点状线表示D和E之间有可能的链路，如果D和E的信道匹配。节点A,B,C和D用信道1与AP相连，节点E和F用信道2和AP相连。节点C和D不能直接和AP相连，需要经过多跳。节点D当前工作在信道1上和AP1相连，如果D切换到信道2上，就可以由经节点E和AP2相连。一旦D和AP2相连，节点B和C也可以由经D和E同AP2相连。节点D有两条路由可以选择，它会选择一条可以获得较好服务质量的路由。

% 在获得信道负载均衡和高信道利用中精确地评估流量负载很重要。依靠每个节点本地地检测流量负载并不能精确地反应实际的负载，因此不能用作选择路由的基础。负载信息应该从AP处获得。当AP在衡量负载时，也应该考虑到距目的地的跳数。当一个节点选择了主路由时，本地负载信息要用来避免路由振荡。AP计算的加权负载（AP-measured weighted load）：负载在AP上计算，但是负载更具从AP到目的的跳数加权。

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/LSelectRoute.jpg}
% \end{figure}

% 当节点获得所有到目的地的可能路由的负载信息后，节点怎样决定什么时候切换信道加入另一棵路由树？考虑图2的场景，使用加权的负载参数，AP1-tree的负载是6Mbps（A1Mbps，D2mbps，G3Mbps），AP2-tree的负载为1Mbps。在这种情况下，如果D切换到信道2，G也会随之切换，这样AP2-tree的负载将会达到8Mbps。所以，只有当前AP1树的负载大于当前AP2加上以D为根的子树根据在AP2-tree上跳数的加权信息，节点D才会切换信道。

% \subsection{路由协议}

% 路由的建立：开始，节点随即选择一个信道，广播SCAN消息，在一段时间内收集应答包，然后切换到下一信道，最终扫描所有的信道。REPLY信息包括应答者的地址，应答者相连的AP的地址和到达AP的跳数。在扫描完所有信道后，节点根据加权的负载metric选择最小负载的路由。节点维护的路由表和AODV类似。

% 路由管理和更新：
% \begin{enumerate}
% \item 计算负载：每个AP记下在过去T秒时间内收到的流量。AP知道目的地，AP记录每个目的地的流量。然后计算路由树的加权负载为所有节点的从目的地（节点）接收到的流量*目的地到达AP的跳数。

% \item 发布和收集负载信息：节点需要获得它所在的路由树和其他路由树上的负载信息，和（其他数）去往节点本身和它的子树中的节点的流量。AP会发送负载信息（包含在HELLO包中），然后节点会在路由表中记下这些值。HELLO包会在所有信道上发送。
% \end{enumerate}

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/LObtainRouteInformation.jpg}
% \end{figure}

% 如图6所示，节点D开始与AP2相连，工作在信道2上。当转发数据包时，D获得自身和C的负载信息，D通过转发AP的HELLO包，也记录下了AP2-tree的负载1500Kbps。节点B在信道2上转发AP1的HELLO包（包括AP1的负载数据300kbps），D收到后发现B以一跳的距离与 AP1相连。D计算由经B到达AP1的负载。

% 则当前D的路由表如图所示：

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/LRouteTableofD.jpg}
% \end{figure}

% O切换路由树以达到负载均衡：如图6所示，节点D计算连接到AP1 后的负载LAP1'=300+(100*2+100*3)=800。仍然小于当前AP2-tree的负载1500，所以D决定切换信道，加入AP1-tree。

% \section{可扩展性}
% \label{sec:scalability}

% 网络的可扩展性可以定义为：在条件A下，随着网络参数B的合理增大，通过性能参数C所衡量的网络仍然能够保持一定的性能。

% WMN技术的有很突出的优势，随着WMN的广泛应用，WMN的可扩展性面临着两个急迫的需求：
% \begin{itemize}
% \item WMN的大面积部署对增大WMN的覆盖面积提出了需求。

% \item 随着WMN用户数量的增加，对增大网络的容量提出了需求。

% \end{itemize}

% 这两项需求实际上是随着WMN规模的增大，对WMN地域上的覆盖范围的扩大和单位面积上用户密度的增加的需求。

% WMN在可扩展性方面同多跳网络一样面临着很多问题，主要有以下几点：
% \begin{itemize}
% \item 多跳网络规模扩大时，网络性能急剧下降。这主要是由于随着WMN规模的扩大，数据传输的路径变长，跳数增加，流量经过的中继增多，随之而来的既是导致整体的吞吐量急剧下降。另一方面，单位面积内用户数量的增多，导致节点之间的竞争和冲突增多，从而也会导致吞吐量的急剧下降。这两点的本质实际上都集中在了更长的路径和更大密度导致了更多的冲突。

% \item 当前的802.11 MAC协议没有对应的标准。当WMN的链路跳数增加到>=4时，吞吐量急剧下降，例如802.11b的TCP吞吐量甚至小于1M。

% \item 现有成熟的集中式多连接方式很难实现。例如TDMA和CDMA，由于其复杂性和诸如TDMA的时钟同步问题等很难在WMN环境下实现。

% \end{itemize}

% 为了解决本质上的冲突，MRMC技术是一种很好的选择。使用多信道的好处是显而易见的，在一条路径上使用多信道技术，就可以实现信道复用。那么处于单个节点信号覆盖的范围内的其他节点使用不同的信道就不会有干扰，也就不会引起冲突。在适当面积内的用户数量增多时，使用多信道技术，即可提高节点密度。

% \subsection{基于环的多信道WMN}

% 第3节对网络容量模型的分析给出了网络容量的上界，具体的方案则尝试改变网络拓扑和一些参数，如天线或信道数量，合理设置这些参数以尽可能地提高网络的容量。在MRMC技术的应用下，J.-H. Huang提出了一个基于环的网络拓扑，在这一拓扑下，改变一些参数，尽可能地获得网络的高扩展性，既覆盖面积和容量。

% 基于环的多信道WMN的结构如下图所示，每个cell中的每个用户以多跳的方式同网关连接，中间节点中继转发到网关的数据流量，网关以有线或无线的方式同骨干网相连。经过应用这种mesh结构，中心网关/AP的服务覆盖面积得到了扩展。

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/SMeshCell.jpg}
% \end{figure}

% 这种基于环的WMN之所以是可扩展的，主要是由于以下两个因素：一是多信道的频率分配可以降低多个用户对同一信道的竞争，克服网关的吞吐量瓶颈问题。二是由于可以调节环的宽度以控制冲突等级，这种环的结构可以便利地管理WMN的吞吐量。

% 在这种基于环的WMN中的频率分配很简单，因为基于环的WMN中只需要考虑到每个环的宽度以保证足够的信道复用距离就好了。一个信道分配的例子如下图所示：一个有3个cell的WMN中的信道分配。信道1-3和4-6指定给每个cell最里面的环A1和A2上的扇区。信道7-9重复分配给中间的环A3和A4。信道10-12单独地分配给环A5。经过4个缓冲环，信道1-3在外层的环A6上复用。这个例子显示了12个可用信道就可以保证两个相同/关联的信道环之间有4个缓冲环。此外，指定给内环的信道可以在足够重用距离的外环上空间复用 [7]。

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/S12channel.jpg}
% \end{figure}

% 为了克服网关附近的瓶颈问题，可以将拥塞的内部环划分为扇区并为每个扇区指定不同的信道。这样可以减少竞争用户的数量，改善吞吐量。显然，如果更多的非重叠信道可以用，那么更多靠近中心的环可以被划分成扇区，消除内环之间的信道干扰，提高cell容量和覆盖面积。多数传统WMN的可扩展性不好，因为当冲突增多时用户吞吐量得不到保证。基于环的WMN是可扩展的，因为基于环的频率分配降低竞争用户的数量以解决竞争问题。假设流量是单向地从用户流向网关。需要考虑用户对向下链路流量的竞争，因此竞争用户的数量会增加。考虑向下链路和向上链路的不对称的流量负载。竞争同一信道的用户也许有不同的流量负载。

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/SSuccessfulTransmission.jpg}
% \end{figure}

% 如图所示，考虑用户P和它的两个受最近的两个邻居$P_L$和$P_R$影响的无线冲突域。其他的用户例如$P'_L$和$P'_R$距离太远而不影响P的区域。如果用户$P_L$或$P_R$在P的无效区域内，用户P可以发RTS请求给用户Q，但是用户Q不能回复CTS。如果$P_L$和$P_R$都不在P的无效区域内，则只有在区域${2A_{W,j}-(X_L+X_R)}$内的用户才可以发送RTS帧。区域$X_L$和$X_R$内的用户不能发送请求，因为他们能感知到$P_L$和$P_R$的传输。

% \subsection{最优覆盖和容量 [7]}

% 覆盖面积和吞吐量之间需要一个折衷。从部署开销的观点看，每个cell覆盖更大区域会更好，因为只需要更少的AP；然而，从链路吞吐量的标准观点来看，更小的cell会更好，因为更短的距离可以获得更高的数据速率。接下来，在考虑到这两个因素的前提下，形式化最优问题以决定每个环的最优半径。

% WMN的最优的覆盖和容量可以公式化为一个混合整形非线性规划问题（MINLP）。定义n为mesh cell中环的数量，$r_1,r_2,...r_n$为相应的环的半径。那么mesh cell的最大吞吐量为：

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/SMAX.jpg}
% \end{figure}

% 约束条件如下：

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/SHC.jpg}
% \end{figure}

% 其中$H_c(i)$是环$A_i$内的最低速率链路的容量，$R_i$是每个节点上的流量负载，$(r_i-r_{i-1})$是环的宽度，$D_{max}$是最大接收范围

% 从模拟的结果来看，基于环的WMN同单跳网络相比增强了cell的覆盖和容量。如下图所示，实验表明，当用户节点所需的流量$R_D$=0.25Mbps时，环的最优数量n=5，当$R_D$=0.5Mbps时环的最优数量n=4。

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/SCapacity.jpg}
% \end{figure}

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/SCoverage.jpg}
% \end{figure}

% 从覆盖面积方面来看，环的划分增强了cell的覆盖面积，当用户节点所需的流量增加时，相应的最优cell覆盖会降低。从最优cell吞吐量来看，也有极大的提高。一般来说mesh cell中环的数量越多，覆盖面积和容量也越大，但是最优的解决方案要考虑到mesh链路吞吐量和节点间距离的限制。

% 由于将内部的环划分为扇区可以降低冲突的用户，克服网关附近的吞吐量瓶颈问题，cell覆盖面积也可以扩大从而服务更多的用户。下图比较了在$R_D$=0.4Mb/s时划分环的扇区对cell覆盖面积的影响。从图中可以观察到如果环$A_1$被划分成扇区，最优的cell覆盖面积可以在n=4时从464m增加到508m。如果环$A_1$和$A_2$都划分扇区，cell的覆盖面积可以在n=6时增长到703m。下图显示了$R_D$=0.4Mb/s时环扇区化后的cell容量效果。环$A_1$扇区话后，cell容量比没有扇区化前增加了20\%，如果间环$A_1$和$A-2$都扇区话，则最优cell容量可提高90\%。

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/SSectorCap.jpg}
% \end{figure}

% \begin{figure}
%   \centering
%   \includegraphics[scale=0.6]{fig/SSectorCov.jpg}
% \end{figure}

% 将cell内部的更多环划分成的扇区可以提高覆盖面积和容量。但是为了将更多的环划分成扇区，需要更多可用的非重叠的信道，因为每个mesh cell需要分配更多的信道以保证足够的缓冲环和复用距离。

\section{结论与展望}
\label{sec:conclusion}

多天线多信道技术为无线多条网络，尤其是Mesh网络带来提高网络容量的机遇，挖掘MRMC的容量潜能在很长一段时间内都将会是研究界的研究热点。

\begin{itemize}
\item 分布式的和动态的信道分配策略将会得到更多的关注。由于集中式的静态的信道分配策略不能很好地适应路由和负载状况的动态变化，所以，使用分布式的动态方案更能满足实际应用需求。
\item 信道分配策略、路由算法和调度策略的联合设计是研究的主流。其中动态的方案还需要更多的研究，在保持动态方案的灵活性的同时，需要考虑方案的优化。
\item 由于无线网络的带宽限制，在设计信道分配和路由算法的过程中，必须考虑QoS和负载均衡的问题，而这两个问题目前还没有得到太多的关注。
\item MRMC Mesh网络的组播路由问题还没有得到很好的解决，这也是一个可能的研究方向。
\end{itemize}

\bibliography{bibliography}

\end{CJK*}
\end{document}
